package leetcode.每日一题;

import leetcode.util.CommonUtils;
import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author ：zsy
 * @date ：Created 2022/10/25 7:55 PM
 * @description：
 */
public class 最短的桥 {
    @Test
    public void test() {
        CommonUtils.arrTransfer("[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]");
        System.out.println(new Solution().shortestBridge(new int[][]{{1, 1, 1, 1, 1}, {1, 0, 0, 0, 1}, {1, 0, 1, 0, 1}, {1, 0, 0, 0, 1}, {1, 1, 1, 1, 1}}));
    }

    class Solution {
        public int shortestBridge(int[][] grid) {
            int n = grid.length;
            int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            List<int[]> island = new ArrayList<>();
            Queue<int[]> queue = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1) {
                        grid[i][j] = -1;
                        queue.offer(new int[]{i, j});
                        while (!queue.isEmpty()) {
                            int[] cur = queue.poll();
                            island.add(cur);
                            for (int k = 0; k < 4; k++) {
                                int[] dir = dirs[k];
                                int curI = dir[0] + cur[0];
                                int curJ = dir[1] + cur[1];
                                if (curI >= 0 && curI < n && curJ >= 0 && curJ < n && grid[curI][curJ] == 1) {
                                    queue.offer(new int[]{curI, curJ});
                                    grid[curI][curJ] = -1;
                                }
                            }
                        }
                    }
                    for (int[] cell : island) {
                        queue.offer(cell);
                    }
                    int step = 0;
                    while (!queue.isEmpty()) {
                        int size = queue.size();
                        for (int k = 0; k < size; k++) {
                            int[] cur = queue.poll();
                            for (int d = 0; d < 4; d++) {
                                int[] dir = dirs[d];
                                int curI = dir[0] + cur[0];
                                int curJ = dir[1] + cur[1];
                                if (curI >= 0 && curI < n && curJ >= 0 && curJ < n) {
                                    if (grid[curI][curJ] == 0) { // 变为1
                                        queue.offer(new int[]{curI, curJ});
                                        grid[curI][curJ] = -1;
                                    } else if (grid[curI][curJ] == 1) {
                                        return step;
                                    }
                                }
                            }
                        }
                        step++;
                    }
                }
            }
            return 0;
        }
    }
}
